package com.jia.leetCode;

/**
 * @program: Leetcode
 * @description: https://leetcode-cn.com/contest/biweekly-contest-17/problems/matrix-block-sum/
 * @author: STU756
 * @create: 2020-08-21 20:28
 */
public class Pro1314 {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int n = mat.length, m = mat[0].length;
        int[][] ans = new int[n][m];
        //矩阵前缀和
        int[][] dp = new int[n + 1][m + 1];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                dp[i+1][j+1] = dp[i+1][j] + dp[i][j+1] - dp[i][j] + mat[i][j];
            }
        }
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                //左上角坐标
                int n1 = Math.max(i - k, 0);
                int m1 = Math.max(j - k, 0);
                //右下角的下标
                int n2 = Math.min(i + k, n - 1);
                int m2 = Math.min(j + k, m - 1);
                ans[i][j] = dp[n2 + 1][m2 + 1] - dp[n1][m2 + 1] - dp[n2 + 1][m1] + dp[n1][m1];

            }
        }
        return ans;
    }
}
